package com.arron.algorithm.leetcodetop100.链表;

import com.arron.algorithm.leetcodetop100.ListNode;

/**
 *148 . 排序链表
 */
public class 排序链表 {



    public static void main(String[] args) {
        int[] a = {4,2,1,3};

       ListNode node = bulidListNode(a);

        sortList(node);
    }
    
    
//    public ListNode sortList(ListNode head) {
//       return sortNode2(head);
//    }


    public ListNode sortNode2(ListNode head){
        if (head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortNode2(head);
        ListNode right = sortNode2(tmp);
        return merge(left,right);
    }

    public ListNode merge(ListNode left,ListNode right){
        ListNode h = new ListNode(0);
        ListNode res = h;
        while (left != null && right != null) {
            if (left.val < right.val) {
                h.next = left;
                left = left.next;
            } else {
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left != null ? left : right;
        return res.next;
    }

    public ListNode sortNode1(ListNode head){

        if (head==null || head.next ==null){
            return head;
        }


        //找中点
        ListNode mid = findMid(head);

        ListNode temp = mid.next;
        mid.next = null;



        ListNode rightHead = sortNode1(temp);

        ListNode leftHead = sortNode1(head);

       return   mergeList(leftHead,rightHead);
    }

    public ListNode findMid(ListNode head){
        if (head==null || head.next ==null ){
            return head;
        }

        ListNode fast = head.next.next;
        ListNode slow = head;

        while (fast!=null&& fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;

        }

       return slow;
    }

   public ListNode  mergeList(ListNode head,ListNode tail){

        ListNode dummyNode = new ListNode(-1);
        ListNode p1 = head;
        ListNode p2 = tail;

        while (true){
            if (p1 ==null){
                dummyNode.next = p2;
                break;
            }
            if (p2 ==null){
                dummyNode.next = p1;
                break;
            }

            if (p1.val > p2.val){
                dummyNode.next = p2;
                p2 = p2.next;
            }else {
                dummyNode.next = p1;
                p1 = p1.next;
            }
            dummyNode = dummyNode.next;
        }
        return dummyNode.next;
   }


    public static ListNode sortList(ListNode head) {
        return sort(head);
    }


    public static ListNode sort(ListNode head){

        //如果链表为空或者链表只有一个节点直接返回
        if (head == null || head.next ==null){
            return head;
        }

        //使用快慢指针找到链表中间节点
        ListNode fastNode = head.next,/*这里注意快指针和慢指针的初始指向，不然会陷入死递归*/slowNode = head,r,l;
        while (fastNode !=null && fastNode.next !=null){
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;
        }

        //1,2,3,4,5,6,7

        //对右边的链表进行排序
        r = sort(slowNode.next);
        //将链表中间节点断开
        slowNode.next = null;
        //在对左边的链表进行排序
        l = sort(head);
        //将两个子链表进行合并排序
        return mergeSortList(r,l);

    }

    public static ListNode mergeSortList(ListNode r, ListNode l){

        ListNode res = new ListNode(0);

        ListNode temp = res;

        while (r!=null && l !=null){

            if (r.val > l.val){
                temp.next = l;
                l = l.next;
            }else {
                temp.next = r;
                r = r.next;
            }
            temp = temp.next;
        }

        if (r != null){
            temp.next = r;
        }

        if (l!= null){
            temp.next = l;
        }
        return res.next;
    }



    public static ListNode bulidListNode(int[] a){

        ListNode res = new ListNode(0);

        ListNode temp = res;
        for (int i = 0; i < a.length; i++) {
            temp.next = new ListNode(a[i]);
            temp = temp.next;
        }
        return res.next;

    }





}
